package tech

import (
	"fmt"
	"slices"
	"ssp/set"
)

func (g *Grid) getURP0() (p0s []*Cell) {
	for _, row := range g.rows {
		for _, p0 := range row.cells {
			if !p0.solved() && p0.cands.Count() == 2 {
				p0s = append(p0s, p0)
			}
		}
	}
	return
}

func (g *Grid) getURP1(p0 *Cell) (p1s []*Cell) {
	for _, cell := range g.rows[p0.rowNum].cells {
		if cell.solved() || cell == p0 {
			continue
		}
		if !cell.cands.IsSuperset(p0.cands) {
			continue
		}
		if cell.cands == p0.cands && cell.colNum < p0.colNum {
			continue
		}
		p1s = append(p1s, cell)
	}
	return
}

func (g *Grid) getURP2(p0 *Cell) (p2s []*Cell) {
	for _, cell := range g.cols[p0.colNum].cells {
		if cell.solved() || cell == p0 {
			continue
		}
		if !cell.cands.IsSuperset(p0.cands) {
			continue
		}
		if cell.cands == p0.cands && cell.rowNum < p0.rowNum {
			continue
		}
		p2s = append(p2s, cell)
	}
	return
}

func (g *Grid) getURP3(p0, p1, p2 *Cell) *Cell {
	p3 := g.rows[p2.rowNum].cells[p1.colNum]
	if p3.solved() || !p3.cands.IsSuperset(p0.cands) {
		return nil
	}
	return p3
}

func (g *Grid) getUR() (rects [][]*Cell) {
	p0s := g.getURP0()
	for _, p0 := range p0s {
		p1s := g.getURP1(p0)
		p2s := g.getURP2(p0)
		for _, p1 := range p1s {
			for _, p2 := range p2s {
				if !withinTwoBoxes([]int{p0.rowNum, p2.rowNum}, []int{p0.colNum, p1.colNum}) {
					continue
				}
				p3 := g.getURP3(p0, p1, p2)
				if p3 != nil {
					rects = append(rects, []*Cell{p0, p1, p2, p3})
				}
			}
		}
	}
	return
}

func urTemplate(g *Grid, doURType func([]*Cell) (bool, []*Result)) (used bool, results []*Result) {
	rects := g.getUR()
	for _, rect := range rects {
		if ok, rs := doURType(rect); ok {
			used = true
			if OUTPUTRESULT {
				results = append(results, rs...)
			}
			if !EXHAUSTIVE {
				return
			}
		}
	}
	return
}
func (s *Solve) UniqueRectangle1(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType1)
}

func (s *Solve) UniqueRectangle2(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType2)
}

func (s *Solve) UniqueRectangle3(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType3)
}

func (s *Solve) UniqueRectangle4A(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4A)
}

func (s *Solve) UniqueRectangle4B(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4B)
}

func (s *Solve) UniqueRectangle4C(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4C)
}

func (s *Solve) UniqueRectangle4D(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4D)
}

func (s *Solve) UniqueRectangle4E(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4E)
}

func (s *Solve) UniqueRectangle4F(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4F)
}

func (s *Solve) UniqueRectangle4G(g *Grid) (used bool, results []*Result) {
	return urTemplate(g, g.doURType4G)
}

func (s *Solve) UniqueRectangle4H(g *Grid) (used bool, results []*Result) {
	return g.uniqueRectangle4H()
}

func (g *Grid) doURType1(rect []*Cell) (used bool, results []*Result) {
	var rmCell *Cell
	count := 0
	for _, cell := range rect[1:] {
		if cell.cands != rect[0].cands {
			rmCell = cell
			count++
		}
	}
	if count != 1 {
		return
	}

	used = true
	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rect[0].cands, []*Cell{rmCell})
		others := []*Cell{}
		for _, cell := range rect {
			if cell != rmCell {
				others = append(others, cell)
			}
		}
		g1 := result.getHelpCandsGroup()
		g1.add(rect[0].cands, others)
		result.setStrategyName("Unique Rectangle Type1")
		results = append(results, result)
	}
	if CHANGE {
		rmCell.removeCands(rect[0].cands)
	}
	return
}

func (g *Grid) doURType2(rect []*Cell) (used bool, results []*Result) {
	zCells := []*Cell{}
	for _, cell := range rect[1:] {
		if cell.cands != rect[0].cands {
			zCells = append(zCells, cell)
		}
	}
	if len(zCells) < 2 {
		return
	}

	cands := zCells[0].cands
	if cands.Count() != 3 {
		return
	}
	for _, cell := range zCells[1:] {
		if cell.cands != cands {
			return
		}
	}

	z := cands.Diff(rect[0].cands)
	if ok, rmCells := g.canRemoveSeenCands(z, zCells); ok {
		used = true
		if OUTPUTRESULT {
			result := new(Result)
			result.addRemoved(z, rmCells)
			g1 := result.getHelpCandsGroup()
			g1.add(z, zCells)
			g2 := result.getHelpCandsGroup()
			g2.add(rect[0].cands, rect)
			result.setStrategyName("Unique Rectangle Type2")
			results = append(results, result)
		}
		if CHANGE {
			removeCands(z, rmCells)
		}
	}
	return
}

func (g *Grid) doURType3Line(rect, zCells []*Cell) (used bool, result *Result) {
	baseCands := rect[0].getCandsOrValue().Union(rect[1].getCandsOrValue())
	var line House
	if zCells[0].rowNum == zCells[1].rowNum {
		line = g.rows[zCells[0].rowNum]
	} else if zCells[0].colNum == zCells[1].colNum {
		line = g.cols[zCells[0].colNum]
	} else {
		return
	}
	cells := []*Cell{}
	for _, cell := range line.cells {
		if cell.solved() || (slices.Contains(zCells, cell)) {
			continue
		}
		cells = append(cells, cell)
	}
	remains := unionCellCands(zCells).Diff(baseCands)
	if ok, subset, subsetCands, rmCells := g.verifyNaked(remains, zCells, cells); ok {
		//fmt.Println("ok", rmCells)
		used = true
		if OUTPUTRESULT {
			result = new(Result)
			result.addRemoved(subsetCands, rmCells)
			g1 := result.getHelpCandsGroup()
			g1.add(subsetCands, append(subset, zCells...))
			g2 := result.getHelpCandsGroup()
			g2.add(baseCands, rect)
			result.setStrategyName("Unique Rectangle Type3")
		}
		if CHANGE {
			removeCands(subsetCands, rmCells)
		}
	}
	return
}

func (g *Grid) doURType3Box(rect, zCells []*Cell) (used bool, result *Result) {
	baseCands := rect[0].getCandsOrValue().Union(rect[1].getCandsOrValue())
	if zCells[0].boxNum != zCells[1].boxNum {
		return
	}

	cells := []*Cell{}
	for _, cell := range g.boxes[zCells[0].boxNum].cells {
		if cell.solved() || (slices.Contains(zCells, cell)) {
			continue
		}
		cells = append(cells, cell)
	}

	remains := unionCellCands(zCells).Diff(baseCands)
	if ok, subset, subsetCands, rmCells := g.verifyNaked(remains, zCells, cells); ok {
		//fmt.Println("ok", rmCells)
		used = true
		if OUTPUTRESULT {
			result = new(Result)
			result.addRemoved(subsetCands, rmCells)
			g1 := result.getHelpCandsGroup()
			g1.add(subsetCands, append(subset, zCells...))
			g2 := result.getHelpCandsGroup()
			g2.add(baseCands, rect)
			result.setStrategyName("Unique Rectangle Type3")
		}
		if CHANGE {
			removeCands(subsetCands, rmCells)
		}
	}
	return
}
func (g *Grid) doURType3(rect []*Cell) (used bool, results []*Result) {
	zCells := []*Cell{}
	for _, cell := range rect[1:] {
		if cell.cands != rect[0].cands {
			zCells = append(zCells, cell)
		}
	}
	if len(zCells) != 2 {
		return
	}

	if (zCells[0].cands == zCells[1].cands) && zCells[0].cands.Count() == 3 {
		return
	}

	var result *Result
	usedLine, resultLine := g.doURType3Line(rect, zCells)
	if usedLine {
		result = resultLine
	}
	usedBox, resultBox := g.doURType3Box(rect, zCells)
	if OUTPUTRESULT && usedBox && (!usedLine || !slices.Equal(resultLine.Removed, resultBox.Removed)) {
		result = resultBox
		if usedLine {
			result = mergeResults(resultLine, resultBox)
		}
	}

	used = usedLine || usedBox

	if used && OUTPUTRESULT {
		results = append(results, result)
	}

	return
}

/*
func (g *Grid) doURType3(rect []*Cell) (used bool, results []*Result) {
	// Validate zCells
	zCells := getZCandidates(rect)
	if len(zCells) != 2 || sameCandidates(zCells) {
		return
	}

	// Process line group (row/col)
	lineGroup, valid := getLineGroup(zCells, g)
	if !valid {
		return
	}

	resultLine, usedInLine := processUR3Group(zCells, rect, lineGroup, g)
	used = usedInLine

	// Process box group if applicable
	if zCells[0].boxNum == zCells[1].boxNum {
		boxCells := getBoxCells(zCells, g)
		resultBox, usedInBox := processUR3Group(zCells, rect, boxCells, g)

		if usedInBox {
			used = true
			resultLine = mergeResults(resultLine, resultBox)
		}
	}

	if OUTPUTRESULT && resultLine != nil {
		results = append(results, resultLine)
	}
	return
}
*/
// Helper functions
func mergeResults(existing *Result, newResult *Result) *Result {
	if existing == nil {
		return newResult
	}
	existing.Removed = append(existing.Removed, newResult.Removed...)
	existing.HelpCands[0] = append(existing.HelpCands[0], newResult.HelpCands[0]...)
	return existing
}

func (g *Grid) doURType4A(rect []*Cell) (used bool, results []*Result) {
	var zCells []*Cell
	var refCell *Cell
	var line House
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	if p2.cands == p0.cands {
		refCell = p2
		zCells = append(zCells, p1, p3)
		line = g.cols[p3.colNum]
	} else if p1.cands == p0.cands {
		refCell = p1
		zCells = append(zCells, p2, p3)
		line = g.rows[p3.rowNum]
	} else {
		return
	}
	onlyTwo := false
	var rmCand set.Set
	for _, cand := range p0.cands.GetList() {
		if onlyCellsHasCand(cand, line, zCells) {
			rmCand = p0.cands.Diff(set.NewSet(cand))
			onlyTwo = true
			break
		}
	}
	if !onlyTwo {
		return
	}
	used = true
	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, zCells)
		g1 := result.getHelpCandsGroup()
		g1.add(p0.cands.Diff(rmCand), zCells)
		g1.add(p0.cands, []*Cell{p0, refCell})
		c := p0.cands.Diff(rmCand).GetList()[0]
		result.addHelpChains(strStrongLink(c, zCells))
		result.setStrategyName("Unique Rectangle Type4A")
		results = append(results, result)
	}
	if CHANGE {
		removeCands(rmCand, zCells)
	}

	return
}

// strStrongLink 生成一个表示两个单元格之间强链接的字符串
// cand: 强链接的候选数
// nodes: 包含两个单元格的切片，这两个单元格之间存在强链接
// 返回值: 格式化的字符串，表示强链接关系
func strStrongLink(cand int, nodes []*Cell) string {
	// 参数验证
	if len(nodes) < 2 || nodes[0] == nil || nodes[1] == nil {
		return "Invalid strong link"
	}

	// 生成格式化的强链接字符串
	// 格式: R行C列[候选数]=R行C列[候选数]
	return fmt.Sprintf("R%vC%v[%v]=R%vC%v[%v]",
		nodes[0].rowNum+1, nodes[0].colNum+1, cand+1,
		nodes[1].rowNum+1, nodes[1].colNum+1, cand+1)
}
func (g *Grid) doURType4B(rect []*Cell) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	if p3.cands != p0.cands || p3.rowNum < p0.rowNum {
		return
	}
	if p1.cands == p0.cands || p2.cands == p0.cands {
		return
	}

	onlyTwo := false
	var rmCand set.Set
	var strongCand int
	for _, cand := range p0.cands.GetList() {
		if onlyCellsHasCand(cand, g.rows[p0.rowNum], []*Cell{p0, p1}) &&
			onlyCellsHasCand(cand, g.rows[p2.rowNum], []*Cell{p2, p3}) &&
			onlyCellsHasCand(cand, g.cols[p0.colNum], []*Cell{p0, p2}) &&
			onlyCellsHasCand(cand, g.cols[p3.colNum], []*Cell{p1, p3}) {
			rmCand = p0.cands.Diff(set.NewSet(cand))
			strongCand = cand
			onlyTwo = true
			break
		}
	}
	if !onlyTwo {
		return
	}

	used = true
	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, []*Cell{p0, p3})
		g1 := result.getHelpCandsGroup()
		g1.add(p0.cands.Diff(rmCand), []*Cell{p0, p3})
		g1.add(p0.cands, []*Cell{p1, p2})
		result.addHelpChains(strStrongLink(strongCand, []*Cell{p0, p1}))
		result.addHelpChains(strStrongLink(strongCand, []*Cell{p0, p2}))
		result.addHelpChains(strStrongLink(strongCand, []*Cell{p3, p1}))
		result.addHelpChains(strStrongLink(strongCand, []*Cell{p3, p2}))
		result.setStrategyName("Unique Rectangle Type4B")
		results = append(results, result)
	}

	if CHANGE {
		removeCands(rmCand, []*Cell{p0, p3})
	}
	return
}

func (g *Grid) doURType4C(rect []*Cell) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	if p1.cands == p0.cands || p2.cands == p0.cands {
		return
	}

	onlyTwo := false
	var rmCand set.Set
	for _, cand := range p0.cands.GetList() {
		if onlyCellsHasCand(cand, g.rows[p3.rowNum], []*Cell{p2, p3}) &&
			onlyCellsHasCand(cand, g.cols[p3.colNum], []*Cell{p1, p3}) {
			rmCand = p0.cands.Diff(set.NewSet(cand))
			onlyTwo = true
			break
		}
	}
	if !onlyTwo {
		return
	}
	used = true
	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, []*Cell{p3})
		c := p0.cands.Diff(rmCand)
		result.addHelpChains(strStrongLink(c.GetList()[0], []*Cell{p3, p1}))
		result.addHelpChains(strStrongLink(c.GetList()[0], []*Cell{p3, p2}))
		g1 := result.getHelpCandsGroup()
		g1.add(p0.cands, []*Cell{p0, p1, p2})
		g1.add(c, []*Cell{p3})
		result.setStrategyName("Unique Rectangle Type4C")
		results = append(results, result)
	}
	if CHANGE {
		removeCands(rmCand, []*Cell{p3})
	}
	return
}

func (g *Grid) doURType4D(rect []*Cell) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]

	var ok bool
	var rmCell *Cell
	var linkCells []*Cell
	var rmCand, linkCand set.Set
	if p1.cands == p0.cands {
		ok, rmCell, rmCand, linkCells, linkCand = g.verifyURType4D(p0, p1, p2, p3)
		if !ok {
			ok, rmCell, rmCand, linkCells, linkCand = g.verifyURType4D(p1, p0, p3, p2)
		}
	} else if p2.cands == p0.cands {
		ok, rmCell, rmCand, linkCells, linkCand = g.verifyURType4D(p0, p2, p1, p3)
		if !ok {
			ok, rmCell, rmCand, linkCells, linkCand = g.verifyURType4D(p2, p0, p3, p1)
		}
	}

	if !ok {
		return
	}
	used = true
	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, []*Cell{rmCell})
		g1 := result.getHelpCandsGroup()
		for _, cell := range []*Cell{p0, p1, p2, p3} {
			if cell == rmCell {
				g1.add(linkCand, []*Cell{rmCell})
			} else {
				g1.add(p0.cands, []*Cell{cell})
			}
		}
		link := fmt.Sprintf("R%vC%v[%v]=R%vC%v[%v]",
			linkCells[0].rowNum+1, linkCells[0].colNum+1, linkCand.ValueString(),
			linkCells[1].rowNum+1, linkCells[1].colNum+1, linkCand.ValueString())
		result.addHelpChains(link)
		result.setStrategyName("Unique Rectangle Type4D")
		results = append(results, result)
	}

	if CHANGE {
		removeCands(rmCand, []*Cell{rmCell})
	}
	return
}

func (g *Grid) doURType4E(rect []*Cell) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	if p0.cands != p3.cands {
		return
	}
	if p1.cands == p0.cands || p2.cands == p0.cands {
		return
	}

	onlyTwo := false
	var rmCand set.Set
	var keptCand set.Set
	var rmCell *Cell
	var otherCells []*Cell
	var chain string
	for _, cand := range p0.cands.GetList() {
		if onlyCellsHasCand(cand, g.rows[p0.rowNum], []*Cell{p0, p1}) {
			rmCand = set.NewSet(cand)
			keptCand = p0.cands.Diff(set.NewSet(cand))
			rmCell = p2
			otherCells = []*Cell{p0, p1, p3}
			onlyTwo = true
			chain = strStrongLink(cand, []*Cell{p0, p1})
			break
		}
		if onlyCellsHasCand(cand, g.cols[p0.colNum], []*Cell{p0, p2}) {
			rmCand = set.NewSet(cand)
			keptCand = p0.cands.Diff(set.NewSet(cand))
			rmCell = p1
			otherCells = []*Cell{p0, p2, p3}
			onlyTwo = true
			chain = strStrongLink(cand, []*Cell{p0, p2})
			break
		}
		if onlyCellsHasCand(cand, g.rows[p3.rowNum], []*Cell{p3, p2}) {
			rmCand = set.NewSet(cand)
			keptCand = p0.cands.Diff(set.NewSet(cand))
			rmCell = p1
			otherCells = []*Cell{p0, p2, p3}
			chain = strStrongLink(cand, []*Cell{p3, p2})
			onlyTwo = true
			break
		}
		if onlyCellsHasCand(cand, g.cols[p3.colNum], []*Cell{p3, p1}) {
			rmCand = set.NewSet(cand)
			keptCand = p0.cands.Diff(set.NewSet(cand))
			rmCell = p2
			otherCells = []*Cell{p0, p1, p3}
			chain = strStrongLink(cand, []*Cell{p3, p1})
			onlyTwo = true
			break
		}
	}
	if !onlyTwo {
		return
	}

	used = true

	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, []*Cell{rmCell})
		g1 := result.getHelpCandsGroup()
		g1.add(keptCand, []*Cell{rmCell})
		g1.add(p0.cands, otherCells)
		result.addHelpChains(chain)
		result.setStrategyName("Unique Rectangle Type4E")
		results = append(results, result)
	}
	if CHANGE {
		removeCands(rmCand, []*Cell{rmCell})
	}
	return
}

func (g *Grid) doURType4F(rect []*Cell) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	if p1.cands == p0.cands || p2.cands == p0.cands || p3.cands == p0.cands {
		return
	}

	found := false
	var rmCand set.Set
	var keptCand set.Set
	var rmCell *Cell
	var otherCells []*Cell
	var chain1, chain2 string
	xy := p0.cands.GetList()
	for i, x := range xy {
		y := xy[1-i]
		if onlyCellsHasCand(x, g.rows[p0.rowNum], []*Cell{p0, p1}) &&
			onlyCellsHasCand(y, g.cols[p1.colNum], []*Cell{p1, p3}) {
			rmCand = set.NewSet(x)
			keptCand = set.NewSet(y)
			rmCell = p2
			otherCells = []*Cell{p0, p1, p3}
			chain1 = strStrongLink(x, []*Cell{p0, p1})
			chain2 = strStrongLink(y, []*Cell{p1, p3})
			found = true
			break
		}
		if onlyCellsHasCand(x, g.cols[p0.colNum], []*Cell{p0, p1}) &&
			onlyCellsHasCand(y, g.rows[p2.rowNum], []*Cell{p2, p3}) {
			rmCand = set.NewSet(x)
			keptCand = set.NewSet(y)
			rmCell = p1
			otherCells = []*Cell{p0, p2, p3}
			chain1 = strStrongLink(x, []*Cell{p0, p2})
			chain2 = strStrongLink(y, []*Cell{p2, p3})
			found = true
			break
		}
	}
	if !found {
		return
	}

	used = true

	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, []*Cell{rmCell})
		g1 := result.getHelpCandsGroup()
		g1.add(keptCand, []*Cell{rmCell})
		g1.add(p0.cands, otherCells)
		result.addHelpChains(chain1)
		result.addHelpChains(chain2)
		result.setStrategyName("Unique Rectangle Type4F")
		results = append(results, result)
	}
	if CHANGE {
		removeCands(rmCand, []*Cell{p0, p3})
	}
	return
}

func (g *Grid) doURType4G(rect []*Cell) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	if p1.cands == p0.cands || p2.cands == p0.cands || p3.cands == p0.cands {
		return
	}

	found := false
	var rmCand set.Set
	var keptCand set.Set
	var rmCell *Cell
	var otherCells []*Cell
	var chain1, chain2 string
	xy := p0.cands.GetList()
	for i, x := range xy {
		y := xy[1-i]
		if onlyCellsHasCand(x, g.cols[p0.colNum], []*Cell{p0, p2}) &&
			onlyCellsHasCand(y, g.cols[p1.colNum], []*Cell{p1, p3}) {
			rmCand = set.NewSet(x)
			keptCand = set.NewSet(y)
			rmCell = p1
			otherCells = []*Cell{p0, p2, p3}
			chain1 = strStrongLink(x, []*Cell{p0, p2})
			chain2 = strStrongLink(y, []*Cell{p1, p3})
			found = true
			break
		}
		if onlyCellsHasCand(x, g.rows[p0.rowNum], []*Cell{p0, p1}) &&
			onlyCellsHasCand(y, g.rows[p2.rowNum], []*Cell{p2, p3}) {
			rmCand = set.NewSet(x)
			keptCand = set.NewSet(y)
			rmCell = p2
			otherCells = []*Cell{p0, p1, p3}
			chain1 = strStrongLink(x, []*Cell{p0, p1})
			chain2 = strStrongLink(y, []*Cell{p2, p3})
			found = true
			break
		}
	}
	if !found {
		return
	}

	used = true

	if OUTPUTRESULT {
		result := new(Result)
		result.addRemoved(rmCand, []*Cell{rmCell})
		g1 := result.getHelpCandsGroup()
		g1.add(keptCand, []*Cell{rmCell})
		g1.add(p0.cands, otherCells)
		result.addHelpChains(chain1)
		result.addHelpChains(chain2)
		result.setStrategyName("Unique Rectangle Type4G")
		results = append(results, result)
	}
	if CHANGE {
		removeCands(rmCand, []*Cell{p0, p3})
	}
	return
}

func getStrongCells(cand int, house House) (cells []*Cell) {
	for _, cell := range house.cells {
		if cell.solved() {
			continue
		}
		if cell.cands.Has(cand) {
			if cell.cands.Count() == 2 {
				return nil
			}
			cells = append(cells, cell)
		}
	}
	if len(cells) != 2 {
		return nil
	}
	return cells
}

func getAnotherStrongCell(cand int, p0 *Cell, house House) (p2 *Cell) {
	for _, cell := range house.cells {
		if cell.solved() || cell == p0 {
			continue
		}
		if cell.cands.Has(cand) {
			if cell.cands.Count() == 2 {
				return nil
			}
			if p2 != nil {
				return nil
			}
			p2 = cell
		}
	}
	return p2
}

func (g *Grid) uniqueRectangle4H() (used bool, results []*Result) {
	for x := range 9 {
		for _, row := range g.rows {
			cells := getStrongCells(x, row)
			if len(cells) != 2 {
				continue
			}
			cands01 := cells[0].cands.Intersect(cells[1].cands)
			for i, p0 := range cells {
				p1 := cells[1-i]
				p2 := getAnotherStrongCell(x, p0, g.cols[p0.colNum])
				if p2 == nil {
					continue
				}
				if !withinTwoBoxes([]int{p0.rowNum, p2.rowNum}, []int{p0.colNum, p1.colNum}) {
					continue
				}
				p3 := g.rows[p2.rowNum].cells[p1.colNum]
				if p3.solved() || p3.cands.Count() < 3 {
					continue
				}
				cands := cands01.Intersect(p2.cands).Intersect(p3.cands)
				if cands.Count() < 2 {
					continue
				}
				for _, y := range cands.Diff(set.NewSet(x)).GetList() {
					if onlyCellsHasCand(y, g.rows[p2.rowNum], []*Cell{p2, p3}) {
						result := new(Result)
						used = true
						if OUTPUTRESULT {
							result = new(Result)
							result.addRemoved(set.NewSet(y), []*Cell{p0})
							g1 := result.getHelpCandsGroup()
							g1.add(set.NewSet(x, y), []*Cell{p1, p2, p3})
							g1.add(set.NewSet(x), []*Cell{p0})
							result.addHelpChains(strStrongLink(x, []*Cell{p0, p1}))
							result.addHelpChains(strStrongLink(x, []*Cell{p0, p2}))
							result.addHelpChains(strStrongLink(y, []*Cell{p2, p3}))
							result.setStrategyName("Unique Rectangle Type6")
							results = append(results, result)
						}
						if CHANGE {
							removeCands(set.NewSet(y), []*Cell{p0})
						}
					} else if onlyCellsHasCand(y, g.cols[p1.colNum], []*Cell{p1, p3}) {
						result := new(Result)
						used = true
						if OUTPUTRESULT {
							result = new(Result)
							result.addRemoved(set.NewSet(y), []*Cell{p0})
							g1 := result.getHelpCandsGroup()
							g1.add(set.NewSet(x, y), []*Cell{p1, p2, p3})
							g1.add(set.NewSet(x), []*Cell{p0})
							result.addHelpChains(strStrongLink(x, []*Cell{p0, p1}))
							result.addHelpChains(strStrongLink(x, []*Cell{p0, p2}))
							result.addHelpChains(strStrongLink(y, []*Cell{p1, p3}))
							result.setStrategyName("Unique Rectangle Type6")
							results = append(results, result)
						}
						if CHANGE {
							removeCands(set.NewSet(y), []*Cell{p0})
						}
					}
				}
			}
		}
	}
	return
}

func (s *Solve) UniqueRectangle4I(g *Grid) (used bool, results []*Result) {
	OUTPUTRESULT = true
	ok, rs := g.CounterDR(g.cdr4)
	if !ok {
		return
	}
	for _, r := range rs {
		if len(r.HelpChains) != 3 {
			continue
		}
		ps := make(map[string]bool)
		for _, chain := range r.HelpChains {
			p1 := chain[:7]
			p2 := chain[8:]
			ps[p1] = true
			ps[p2] = true
		}
		if len(ps) == 5 {
			continue
		}
		results = append(results, r)
		used = true
	}
	OUTPUTRESULT = false
	return
}

func (s *Solve) URAndWing(g *Grid) (used bool, results []*Result) {
	alsStrongs := g.initNWingStrongs()
	rects := g.getUR()
	for _, rect := range rects {
		if ok, rs := g.doURAndWing(rect, alsStrongs); ok {
			used = true
			if OUTPUTRESULT {
				results = append(results, rs...)
			}
			if !EXHAUSTIVE {
				return
			}
		}
	}
	return
}

func (g *Grid) doURAndWing(rect []*Cell, alsStrongs map[GroupItem][]GroupItem) (used bool, results []*Result) {
	p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
	var pivots []*Cell
	for _, pivot := range rect[1:] {
		if pivot.cands != p0.cands {
			pivots = append(pivots, pivot)
		}
	}
	if len(pivots) != 2 {
		return
	}

	/*
		if p0.cands == p1.cands {
			pivots = []*Cell{p2, p3}
		} else if p0.cands == p2.cands {
			pivots = []*Cell{p1, p3}
		} else {
			return
		}
	*/
	heads := []GroupItem{}
	for _, pivot := range pivots {
		for _, cand := range pivot.cands.Diff(p0.cands).GetList() {
			heads = append(heads, GroupItem{cand: cand, group: [9]*Cell{pivot}})
		}
	}
	//fmt.Println(p0, p1, p2, p3, heads)
	if ok, itemsss := g.findNWingChains(heads, alsStrongs); ok {
		used = true
		for _, itemss := range itemsss {
			z := itemss[0][len(itemss[0])-1].cand
			zs := []*Cell{}
			for _, items := range itemss {
				for _, cell := range items[len(items)-2].group {
					if cell == nil {
						break
					}
					if !cell.cands.Has(z) {
						continue
					}
					zs = append(zs, cell)
				}
			}
			if ok, rmCells := g.canRemoveSeenCands(set.NewSet(z), zs); ok {
				result := new(Result)
				result.addRemoved(set.NewSet(z), rmCells)
				result.setStrategyName("URAndWing")
				g1 := result.getHelpCandsGroup()
				g1.add(p0.cands, []*Cell{p0, p1, p2, p3})
				g2 := result.getHelpCandsGroup()
				for _, cell := range pivots {
					g2.add(cell.cands.Diff(p0.cands), []*Cell{cell})
				}
				g3 := result.getHelpCandsGroup()
				for _, items := range itemss {
					if len(items) != 4 {
						continue
					}
					for _, cell := range items[1].getCells() {
						g2.add(set.NewSet(items[1].cand), []*Cell{cell})
					}
					for _, cell := range items[2].getCells() {
						g3.add(set.NewSet(items[2].cand), []*Cell{cell})
					}
				}

				cellss := [][]*Cell{}
				for _, items := range itemss {
					if len(items) != 4 {
						continue
					}
					cellss = append(cellss, items[2].getCells())
				}
				slices.SortFunc(cellss, compareCells)
				cellss = slices.CompactFunc(cellss, slices.Equal)
				for _, cells := range cellss {
					result.addHelpCells(cells)
				}

				results = append(results, result)
				used = true
			}
		}
	}

	return
}

/*
	func (g *Grid) doURAndWing(rect []*Cell) (used bool, results []*Result) {
		p0, p1, p2, p3 := rect[0], rect[1], rect[2], rect[3]
		var pivots []*Cell
		if p0.cands == p1.cands {
			pivots = []*Cell{p2, p3}
		} else if p0.cands == p2.cands {
			pivots = []*Cell{p1, p3}
		} else {
			return
		}

		pivotCands := unionCellCands(pivots).Diff(p0.cands)
		allWings, allZ := g.findURWings(pivotCands, pivots)
		for i, wings := range allWings {
			z := allZ[i]
			if ok, rmCells := g.canRemoveSeenCands(set.NewSet(z), wings); ok {
				used = true
				if CHANGE {
					removeCands(set.NewSet(z), rmCells)
				}
				if OUTPUTRESULT {
					result := new(Result)
					result.addRemoved(set.NewSet(z), rmCells)
					g1 := result.getHelpCandsGroup()
					for _, cell := range []*Cell{p0, p1, p2, p3} {
						if slices.Contains(rmCells, cell) {
							//fmt.Println("######", p0.cands.Diff(set.NewSet(z)), z, cell, rmCells)
							g1.add(p0.cands.Diff(set.NewSet(z)), []*Cell{cell})
						} else {
							g1.add(p0.cands, []*Cell{cell})
						}
					}
					g2 := result.getHelpCandsGroup()
					g2.add(pivotCands, pivots)
					g2.add(pivotCands, wings)
					g3 := result.getHelpCandsGroup()
					g3.add(set.NewSet(z), wings)
					result.setStrategyName("Unique Rectangle and Wing")
					results = append(results, result)
				}
				if !EXHAUSTIVE {
					return
				}
			}
		}

		return
	}
*/
func withinTwoBoxes(rowNums, colNums []int) bool {
	return (rowNums[0]/3 == rowNums[1]/3 && colNums[0]/3 != colNums[1]/3) ||
		(rowNums[0]/3 != rowNums[1]/3 && colNums[0]/3 == colNums[1]/3)
}

/*
	func (g *Grid) canRemoveSeenCands(cands set.Set, cells []*Cell) (used bool, rmCells []*Cell) {
		shares := g.seenCells(cells[0])
		for _, cell := range cells[1:] {
			shares = shareCells(shares, g.seenCells(cell))
		}

		for _, cell := range shares {
			if cell.canRemoveCands(cands) {
				rmCells = append(rmCells, cell)
				used = true
			}
		}
		return
	}
*/
func (g *Grid) verifyNaked(cands set.Set, zCells []*Cell, cells []*Cell) (
	ok bool, subset []*Cell, subsetCands set.Set, rmCells []*Cell) {
	var found bool
	for i := 1; i < len(cells); i++ {
		found = false
		for _, subset = range combine(cells, i) {
			subsetCands = cands.Union(unionCellCands(subset))
			if subsetCands.Count() == len(subset)+1 {
				found = true
				break
			}
		}
		if found {
			break
		}
	}
	//fmt.Println("\t", subset, subsetCands)
	if !found {
		return
	}
	for _, cell := range cells {
		if slices.Contains(subset, cell) {
			continue
		}
		if cell.canRemoveCands(subsetCands) {
			ok = true
			rmCells = append(rmCells, cell)
		}
	}

	return
}

func (g *Grid) verifyHidden(remainCands set.Set, zCells []*Cell, cells []*Cell) (
	ok bool, subset []*Cell, subsetCands set.Set, rmCells []*Cell) {
	cands := zCells[0].cands.Union(zCells[1].cands).Diff(remainCands)
	//fmt.Println("\t", remainCands.ValueString(), cands.ValueString(), zCells, cells)
	var found bool
	for i := 1; i < len(cells); i++ {
		found = false
		for _, subset = range combine(cells, i) {
			hiddenCands := cands
			otherCands := remainCands
			for _, cell := range cells {
				if cell.isMemberOf(subset) {
					hiddenCands = hiddenCands.Union(cell.cands)
				} else {
					otherCands = otherCands.Union(cell.cands)
				}
			}
			subsetCands = hiddenCands.Diff(otherCands)
			if subsetCands.Count() == len(subset)+1 {
				found = true
				break
			}
		}
		if found {
			break
		}
	}
	//fmt.Println("\t", subset, subsetCands)
	if !found {
		return
	}
	for _, cell := range subset {
		if cell.canRemoveCands(set.NewFull().Diff(subsetCands)) {
			rmCells = append(rmCells, cell)
			ok = true
		}
	}

	return
}

func onlyCellsHasCand(cand int, house House, butCells []*Cell) bool {
	for _, cell := range house.cells {
		if cell.solved() {
			continue
		}
		if slices.Contains(butCells, cell) {
			if !cell.cands.Has(cand) {
				return false
			}
		} else {
			if cell.cands.Has(cand) {
				return false
			}
		}
	}
	return true
}

func (g *Grid) verifyURType4D(p0, p1, p2, p3 *Cell) (ok bool,
	rmCell *Cell, rmCand set.Set, linkCells []*Cell, linkCand set.Set) {
	for _, cand := range p0.cands.GetList() {
		var line House
		if p0.rowNum == p2.rowNum {
			line = g.rows[p0.rowNum]
		} else {
			line = g.cols[p0.colNum]
		}
		if onlyCellsHasCand(cand, line, []*Cell{p0, p2}) {
			ok = true
			rmCell = p3
			rmCand = p0.cands.Diff(set.NewSet(cand))
			linkCells = []*Cell{p0, p2}
			linkCand = set.NewSet(cand)
			return
		}

		if p0.rowNum == p1.rowNum {
			line = g.rows[p0.rowNum]
		} else {
			line = g.cols[p0.colNum]
		}
		if onlyCellsHasCand(cand, line, []*Cell{p1, p3}) {
			ok = true
			rmCell = p2
			rmCand = p0.cands.Diff(set.NewSet(cand))
			linkCells = []*Cell{p1, p3}
			linkCand = set.NewSet(cand)
			return
		}
	}
	return
}

/*
func (g *Grid) findURWings(pivotCands set.Set, pivots []*Cell) (allWings [][]*Cell, allZ []int) {
	candWings := make(map[int][]*Cell)
	var zs set.Set
	for _, cand := range pivotCands.GetList() {
		seenCells := []*Cell{}
		if pivots[0].cands.Has(cand) && !pivots[1].cands.Has(cand) {
			seenCells = g.seenCells(pivots[0])
		} else if !pivots[0].cands.Has(cand) && pivots[1].cands.Has(cand) {
			seenCells = g.seenCells(pivots[1])
		} else if pivots[0].cands.Has(cand) && pivots[1].cands.Has(cand) {
			seenCells = shareCells(g.seenCells(pivots[0]), g.seenCells(pivots[1]))
		}
		for _, cell := range seenCells {
			if slices.Contains(pivots, cell) {
				continue
			}
			if cell.cands.Count() == 2 && cell.cands.Intersect(pivotCands) == set.NewSet(cand) {
				candWings[cand] = append(candWings[cand], cell)
				zs = zs.Union(cell.cands)
			}
		}
	}
	zs = zs.Diff(pivotCands)
	for _, z := range zs.GetList() {
		wings := []*Cell{}
		for _, cand := range pivotCands.GetList() {
			for _, cell := range candWings[cand] {
				if cell.cands.Has(z) {
					wings = append(wings, cell)
				}
			}
		}
		if len(wings) == pivotCands.Count() {
			allWings = append(allWings, wings)
			allZ = append(allZ, z)
		}
	}

	return
}
*/
